import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

/*
 * @lc app=leetcode.cn id=1005 lang=java
 *
 * [1005] K 次取反后最大化的数组和
 */

// @lc code=start
class Solution {

    public int largestSumAfterKNegations(int[] nums, int k) {
         List<Integer> list=new ArrayList<>(nums.length);
         for(int i=0;i<nums.length;i++){
            list.add(nums[i]);
         }
         Collections.sort(list,new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return Math.abs(o1)-Math.abs(o2);
            }
         });//按绝对值从小到达排序
        for(int i=list.size()-1;i>=0;i--){
            if(list.get(i)<0){
                k--;
                list.set(i, list.get(i)*-1);
                if(k==0){
                    break;
                }
            }
        }
        if(k%2==1){//将最小的转换为负数
            list.set(0, list.get(0)*-1);
        }
        int sum=0;
        for(int i=0;i<list.size();i++){
            sum+=list.get(i);
        }
        return sum;
    }
}
// @lc code=end

